package com.wrial.middle;
/*
 * @Author  Wrial
 * @Date Created in 17:41 2020/8/3
 * @Description
 */

import java.util.Arrays;

public class LeetCode_43_字符串相乘 {

    /**
     * 核心思想就是乘法列式子，要注意的点就是除了最低位，其余为需要补0，而且string相加是逆序需要reverse的
     * 然后就是逐个相乘，最后将每组结果相加
     *  num1的第i位(高位从0开始)和num2的第j位相乘的结果在乘积中的位置是[i+j, i+j+1]
     *         例: 123 * 45,  123的第1位 2 和45的第0位 4 乘积 08 存放在结果的第[1, 2]位中
     *           index:    0 1 2 3 4
     *
     *                         1 2 3
     *                     *     4 5
     *                     ---------
     *                           1 5
     *                         1 0
     *                       0 5
     *                     ---------
     *                       0 6 1 5
     *                         1 2
     *                       0 8
     *                     0 4
     *                     ---------
     *                     0 5 5 3 5
     * @param num1
     * @param num2
     * @return
     */
    public static String multiply(String num1, String num2) {
        if (num1.equals("0")||num2.equals("0")) return "0";
        String res = "";
        for (int j = num2.length() - 1; j >= 0; j--) {
            //需要carry记录每次乘法的进位   需要对除过个位的数字相乘补响相应的0(因为最后相加的时候需要逆序，所以append要提前加0)
            StringBuilder builder = new StringBuilder();
            int carry = 0;
            //补0
            for (int zero = 0; zero < num2.length() - 1 - j; zero++) {
                builder.append(0);
            }
            for (int i = num1.length() - 1; i >= 0; i--) {
                int temp = (num1.charAt(i) - '0') * (num2.charAt(j) - '0') + carry;
                carry = temp / 10;
                builder.append(temp % 10);
            }
            if (carry != 0) {
                builder.append(carry);
            }
            res = totalAdd(res, builder.reverse().toString());
        }
        return res;
    }

    private static String totalAdd(String res, String newStr) {
        System.out.println("res"+res+"new"+newStr);
        StringBuilder builder = new StringBuilder();
        int carry = 0, i = res.length() - 1, j = newStr.length() - 1;
        while (i >= 0 || j >= 0 || carry != 0) {
            int temp = 0;
            temp += i >= 0 ? res.charAt(i--) - '0' : 0;
            temp += j >= 0 ? newStr.charAt(j--) - '0' : 0;
            temp += carry;
            carry = temp / 10;
            builder.append(temp % 10);
        }
        return builder.reverse().toString();
    }

    public static void main(String[] args) {
        multiply("11", "11");
    }
}
